#include<iostream>
#include<cstring>
#include<queue>

using namespace std;
const int N=510;

typedef pair<int,int> pll;
int n,m,ans;
int map[N][N],dist[N][N];
bool st[N][N],flag;
int dx[4]={0,-1,0,1},dy[4]={-1,0,1,0};
queue<pll> q; 

inline void dfs(int x,int y,int sum,int color)
{
	if(x==n && y==n)
	{
		ans=min(ans,step);
		return;
	}
	for(int i=0;i<4;i++)
	{
		int xx=x+dx[i];
		int yy=y+dy[i];
		if(xx<=n && xx>=1 && yy<=n && yy>=1 && st[xx][yy]==0)
		{
			if(map[xx][yy]!=2)
			{
				if(map[xx][yy]==color)
			}
		}
	}
}

int main()
{
	scanf("%d%d",&n,&m);
	memset(map,2,sizeof map);
	memset(dist,-1,sizeof dist);
	for(int i=1;i<=m;i++)
	{
		int x,y,k;
		scanf("%d%d%d",&x,&y,&k);
		map[x][y]=k;
	}
	bfs(1,1);
	if(dist[n][n]==-1) cout<<"-1"<<endl;
	else
	{
		cout<<ans<<endl;
	}
	return 0;
 } 
